import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        boolean[] flag = new boolean[n];
        if (n < 4) return ans;
        Arrays.sort(nums);
        process(nums, 0, 0, target, flag);
        return ans;
    }

    public void process(int[] nums, int n, int i, int target, boolean[] flag) {
        if (n == 4 || i == nums.length) {
            if (n == 4 && target == 0) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        if (nums.length - i > (4 - n)) {
            process(nums, n, i + 1, target, flag);
        }
        if ((i != 0 && nums[i] == nums[i - 1] && !flag[i - 1]) ||
                (target - nums[i] < 0 && nums[i] > 0)) return;
        flag[i] = true;
        list.add(nums[i]);
        process(nums, n + 1, i + 1, target - nums[i], flag);
        list.remove(list.size() - 1);
        flag[i] = false;
    }
}
